Section: Partnerships and Cooperations

National Initiatives

ANR CMON

Participants : François Baccelli, Florence Bénézit, Darryl Veitch.

The ANR project CMON, jointly with Technicolor, LIP6, the Inria project-team Planète and the community http://wiki.grenouille.com/index.php/CMON was continued for 6 months. This project is focused on the development of end-to-end measurement for Internet that can be deployed by end-users, without any support from ISP. Our work over this period focused on wireless network tomography.

ANR PEGASE

Participants : Abir Benabid, Anne Bouillard.

TREC is a partner of the 3-year ANR project called PEGASE, jointly with ENS Lyon, the Inria project-team MESCAL, ONERA, Real-Time-at-Work (start-up) and Thalès. This project is focused on the analysis of critical embedded networks using algebraic tools. The aim is to apply these techniques to AFDX and Spacewire architectures. Abir Benabid was hired until January 2012.

ANR GAP

Participants : Marc Lelarge, Emilie Coupechoux, Mathieu Leconte.

Over the last few years, several research areas have witnessed important progress through the fruitful collaboration of mathematicians, theoretical physicists and computer scientists. One of them is the cavity method. Originating from the theory of mean field spin glasses, it is key to understanding the structure of Gibbs measures on diluted random graphs, which play a key role in many applications, ranging from statistical inference to optimization, coding and social sciences.

The objective of this project (2012-2016) is to develop mathematical tools in order to contribute to a rigorous formalization of the cavity method. We intend to launch two new research lines:

• From local to global, the cavity method on diluted graphs. We will study the extent to which the global properties of a random process defined on some graph are determined by the local properties of interactions on this graph. To this end, we will relate the cavity method to the analysis of the complex zeros of the partition function, an approach that also comes from statistical mechanics. This will allow us to apply new techniques to the study of random processes on large diluted graphs and associated random matrices.

• Combinatorial optimization, network algorithms, statistical inference and social sciences. Motivated by combinatorial optimization problems, we will attack long-standing open questions in theoretical computer science with the new tools developed in the first project. We expect to design new distributed algorithms for communication networks and new algorithms for inference in graphical models. We will also analyze networks from an economic perspective by studying games on complex networks.

ANR MAGNUM

Participant : Ana Bušić.

Ana Bušić is participating (pôle de rattachement: LIP6, UPMC) in the 4-year ANR project MAGNUM (Méthodes Algorithmiques pour la Génération aléatoire Non Uniforme: Modèles et applications), 2010–2014; http://www.lix.polytechnique.fr/~rossin/ANR/Magnum/www/ . The central theme of the MAGNUM project is the elaboration of complex discrete models that are of broad applicability in several areas of computer science. A major motivation for the development of such models is the design and analysis of efficient algorithms dedicated to simulation of large discrete systems and random generation of large combinatorial structures.

GdR Stochastic Geometry

Participants : François Baccelli, Bartłomiej Błaszczyszyn.

TREC is a member of the Research Group GeoSto (Groupement de recherche, GdR 3477) http://gdr-geostoch.math.cnrs.fr/ on Stochastic Geometry led by Pierre Calka (Université de Rouen). This is a collaboration framework for all French research teams working in the domain of spatial stochastic modeling, both on theory development and in applications. The kickoff meeting was organized this year in March at the University of Rouen; http://gdr-geostoch.math.cnrs.fr/workshop_Rouen . It brought together more than 80 researchers from France and Europe.

ARC OCOQS

Participant : Ana Bušić.

Two-year Inria Collaborative action Action de recherche collaborative (ARC) OCOQS “Optimal threshold policies in COntrolled Queuing Systems” OCOQS started in 2011. Coordinator: Ana Bušić, Participants: Alain Jean-Marie (MAESTRO, Inria Sophia-Antipolis), Emmanuel Hyon (University of Paris Ouest and LIP6), Ingrid Vliegen (University of Twente); http://www.di.ens.fr/~busic/OCOQS . The research subject is the optimal control of stochastic processes, with applications to the control of networks and manufacturing systems. The principal aim is to widen the set of mathematical techniques that can be used to prove that optimal policies are of threshold type, thereby widening the set of classes of models that can be effectively solved exactly or numerically handled in practice. A one-day workshop on Structural Properties in Markov Decision Processes was organized this year in January at Inria, Paris; http://www.di.ens.fr/~busic/OCOQS/workshop.html .